在寫題目時遇到的一個主題~前面已經對迴圈有基本認識了，現在用另一種思路把迴圈改寫成遞迴方式，所以在這邊做個紀錄。

什麼是遞迴

先看MDN說明：

The act of a function calling itself, recursion is used to solve problems that contain smaller sub-problems. A recursive function can receive two inputs: a base case (ends recursion) or a recursive case (resumes recursion).

簡單說函式呼叫自身來解決問題的方法。遞迴的過程有點像是俄羅斯娃娃，不斷的打開每一層，直到最小的一個(base case)。

遞迴的核心是將一個大問題拆解成更小的子問題，每一步都在處理這個子問題，直到問題無法再拆解，然後逐步回溯解決。

遞迴基本要素

• recursive case：自己呼叫自己
• base case：要有停止條件，跟迴圈一樣，避免無限遞迴

範例：計算累加，使用遞迴寫法

function sum(n) {
  let result = 0;
  if (n === 1) {
    return 1;
  }
  return n + sum(n - 1);
}
console.log(sum(5)); //15

這裡的執行過程：
sum(5) 呼叫 sum(4) ，結果為5 + sum(4)
sum(4) 呼叫 sum(3) ，結果為4 + sum(3)
直到 sum(1) 回傳 1 ，開始回溯累加：

「執行過程」的地方是由上到下，直到 sum(1) 回傳 1 ，對照到表格「回傳累加」的地方，再由下往上累加上去。所以結果15是這樣來的~

改成迴圈寫法：

function sum(n) {
  let result = 0;
  for (let i = 0; i <= n; i++) {
    result += i;
  }
  return result;
}
console.log(sum(5)); //15

遞迴要注意的地方

遞迴的問題：function還沒執行完又呼叫自己，會一直堆疊function，也會占用大量記憶體空間，所以深度太深會導致堆疊溢位(stack overflow)！

以上分享~謝謝

參考資料

MDN - Recursion
JavaScript 學演算法（二十二）- 遞迴 Recursion
wikipedia - 遞迴
一次看懂遞迴 (Recursion) 的思維模式（一）